#include "node.h"

class Solution {
  public:
    /**
     * @param pHead1 Node类
     * @param pHead2 Node类
     * @return Node类
     */
    Node* Merge(Node* pHead1, Node* pHead2) {
        //! 创建一个虚拟头节点
        Node dummy(0);
        Node* current = &dummy;

        //! 遍历两个链表，直到其中一个链表为空
        while (pHead1 && pHead2) {
            if (pHead1->val < pHead2->val) {
                current->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                current->next = pHead2;
                pHead2 = pHead2->next;
            }
            current = current->next;
        }

        //! 将剩余的链表直接连接到新链表的末尾
        if (pHead1) {
            current->next = pHead1;
        } else {
            current->next = pHead2;
        }

        //! 返回新链表的头节点
        return dummy.next;
    }
};